#include <gtest/gtest.h>

#include <iostream>
#include <numeric>
#include <string>
#include <vector>

using namespace std;

class Solution {
 public:
  int minCut(string s) {
    int n = s.size();
    vector<vector<bool>> g(n, vector<bool>(n, false));
    // construct palindrome map
    for (int end = 0; end < n; end++) {
      for (int start = 0; start <= end; start++) {
        if (s[start] == s[end] && (end - start < 2 || g[start + 1][end - 1])) {
          g[start][end] = true;
        }
      }
    }
    // define dp[n], dp[x] means min Cut
    vector<int> dp(n);
    iota(dp.begin(), dp.end(), 0);
    for (int end = 1; end < n; end++) {
      for (int start = 0; start <= end; start++) {
        if (g[start][end]) {
          dp[end] = min(dp[end], start ? dp[start - 1] + 1 : 0);
        }
      }
    }
    return dp[n - 1];
  }
};

int main() {
  Solution a;
  cout << a.minCut("aaaa") << endl;
  cout << a.minCut("aab") << endl;
  cout << a.minCut("a") << endl;
  cout << a.minCut("ab") << endl;
  return 0;
}
